package com.example.demo.arithmetic.algorithm.dynamic_programing;

/**
 * 最长公共字串 动态规划求解
 */


/*
找规律 进而求得递推公式
    i   t   h   e   i   m   a
t   0   1   0   0   0   0   0

h   0   0   2   0   0   0   0

e   0   0   0   3   0   0   0    3即最长公共字串

m   0   0   0   0   0   1   0

a   0   0   0   0   0   0   2

if(相同字符）
{
    dp[i][j] = dp[i-1][j-1]+1
}else{
    dp[i][j]=0
}

 */
public class LCSubstring {
    public static void main(String[] args) {
        //        System.out.println(lcs("itheima", "thema"));
        // str1 = "abcwerhrlloyuiodef" str2 = "cvhellobnm"
        System.out.println(lcs("abcwerhrlloyuiodef", "cvhellobnm"));
    }

    public static int lcs(String a, String b) {
        int[][] dp = new int[b.length()][a.length()];
        char[] arrayA = a.toCharArray();
        char[] arrayB = b.toCharArray();

        // 优化
        //        for (int i = 0; i < arrayB.length; i++) {
        //            if (arrayA[i] == arrayB[0]) {
        //                dp[0][i] = 1;
        //            }
        //
        //        }
        int max = 0;
        for (int i = 0; i < arrayB.length; i++) {
            for (int j = 0; j < arrayA.length; j++) {
                if (arrayA[j] == arrayB[i]) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    max = Math.max(max, dp[i][j]);
                }
            }

            //            printDp(dp);
        }
        return max;
    }


    private static void printDp(int[][] arr) {
        for (int[] its : arr) {
            for (int anInt : its) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}
